package class_5;

public class Coding_EhrlichAndEuler {
	/**
	 * 埃氏筛
	 * @param n 正整数
	 * @return
	 */
	public static int enrlich(int n) {
		//统计2~n之间有多少个质数
		boolean[] visit = new boolean[n+1];
		//初始默认Fasle， 即2~n的数都为质数
		for(int i=2;i<=n;i++) {
			if(!visit[i]) {
				//打标记
				for(int j=i*i; j<=n; j+=i) {
					visit[j] = true;
				}
			}
		}
		
		int cnt = 0;
		for(int i=2;i<=n;i++) {
			if(!visit[i]) {
				//i是质数， 可以++
				cnt++;
			}
		}
		return cnt;
	}
	
	public static int eular(int n) {
		boolean[] visit = new boolean[n+1];
		int[] prime = new int[n/2+1];//记录0~n范围的质数
		int cnt = 0;//质数的个数。
		//手写顺序表
		for(int i=2;i<=n;i++) {
			if(!visit[i]) {
				prime[cnt++] = i;
			}
			//遍历顺序表
			for(int j=0;j<cnt;j++) {
				if(i * prime[j] > n) {
					break;
				}
				//标记
				visit[i * prime[j]] = true;
				
				if(i % j == 0) {
					break;
				}
			}
		}
		return cnt;
	}
	
	public static int enrlich2(int n) {

		//统计2~n之间有多少个质数
		boolean[] visit = new boolean[n+1];
		//初始默认Fasle， 即2~n的数都为质数
		int cnt = (n+1)/2;
		for(int i=3;i*i<=n;i+=2) {
			if(!visit[i]) {
				for(int j=i*i;j<=n;j+=2*i) {
					if(!visit[j]) {
						visit[j] = true;
						cnt--;
					}
				}
			}
		}
		return cnt;
	}
}
